package 刷题10月.数组;
// https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=188&&tqId=38596&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
public class NC74数字在升序数组中出现的次数0930二分法 {
    /*
    思路：
    二分法 找到k的位置mid，然后k必然在left和right之间，遍历即可
     */
    public class Solution {
        public int GetNumberOfK(int [] array , int k) {
            int left=0,right=array.length-1;
            int mid=0;
            int count=0;
            //二分法 找到k的位置mid，然后k必然在left和right之间，遍历即可
            while(left<right){
                mid=left+(right-left)/2;
                if(array[mid]==k){
                    break;
                }
                if(array[mid]<k){
                    left=mid+1;
                }
                else{
                    right=mid-1;
                }
            }
            for(int i=left;i<=right;i++){
                if(array[i]==k){
                    count++;
                }
            }
            return count;
        }
    }
}
/*
题目:统计一个数字在排序数组中出现的次数;
参数:1.传入的有序数组;2.查找的数字
思路:看到很多人采用二分查找的方法;自己写了一个类似于双指针的方法。
①:准备两个指针,遍历数组,查找是否有与指定数字相等的元素;
②:如果存在,则小指针记录下第一个等于k的索引值;
③:大指针继续向下移动,寻找小指针之后第一个与k不相等的元素索引,记录下索引值,如果一相等的话;则大指针为数组的长度值;
④返回的是大指针减去小指针的值;
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null){
            return 0;
        }
        int smallPoint=0;
        int bigPoint=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==k){
                smallPoint=i;
                break;
            }
        }
        for(int i=smallPoint;i<array.length;i++){
            if(array[i]!=k){
                bigPoint=i;
                break;
            }else{
                 bigPoint=array.length;
            }
        }
        return bigPoint-smallPoint;
    }
}
 */
